package com.learn.algorlthm;

import java.util.LinkedList;

/**
 * @classname:
 * @Description:序列化二叉树
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-04 14:49
 * 题目描述：
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 */
public class Learn37 {

   private static String desserializeStr;

   //序列化
   public static String serialize(TreeNode treeNode) {
      if (treeNode == null)
         return "#";
      return treeNode.value + " " + serialize(treeNode.left) + " " + serialize(treeNode.right);
   }

   public static TreeNode desSerialize(String str){
      desserializeStr = str;
      TreeNode treeNode = desSerialize();
      return treeNode;
   }

   public static TreeNode desSerialize() {
      if (desserializeStr == null || desserializeStr.isEmpty())
         return null;

      int index = desserializeStr.indexOf(" ");
      String value = index == -1 ? desserializeStr : desserializeStr.substring(0, index);
      desserializeStr = index == -1 ? "" : desserializeStr.substring(index + 1);

      if (value.equals("#"))
         return null;
      TreeNode t = new TreeNode(Integer.valueOf(value));
      t.left = desSerialize();
      t.right = desSerialize();
      return t;
   }



   public static TreeNode getTreeNode() {
//        int[] values = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 ,18, 19, 20};
      int[] values = {1 ,2, 3, 4, 5, 6, 7};

      LinkedList<TreeNode> list = new LinkedList<>();
      for (int value : values) {
         list.add(new TreeNode(value));
      }

      for (int preIndex = 0; preIndex < values.length/2 -1; preIndex++) {

         TreeNode node = list.get(preIndex);
         node.left = list.get(preIndex *2 + 1);
         node.right = list.get(preIndex * 2 + 2);
      }

      int lastIndex = values.length/2 - 1;
      list.get(lastIndex).left = list.get(lastIndex * 2 +1);
      if (values.length % 2 != 0)
         list.get(lastIndex).right = list.get(lastIndex * 2 +2);


      return list.get(0);
   }

   static class TreeNode{
      public int value;

      public TreeNode left;
      public TreeNode right;

      public TreeNode() {
      }

      public TreeNode(int value) {
         this.value = value;
      }
   }

}
